Intersection of three sorted arrays

Time: O(N); Space: O(1); easy

Given three integer arrays arr1, arr2 and arr3 sorted in strictly increasing order, return a sorted array of only the integers that appeared in all three arrays.

Example 1:

Input: arr1 = [1,2,3,4,5], arr2 = [1,2,5,7,9], arr3 = [1,3,4,5,8]

Output: [1,5]

Explanation:

• Only 1 and 5 appeared in the three arrays.

Constraints:

• 1 <= len(arr1), len(arr2), len(arr3) <= 1000

• 1 <= arr1[i], arr2[i], arr3[i] <= 2000

class Solution1(object):
    """
    Time: O(N)
    Space: O(1)
    """
    def arraysIntersection(self, arr1, arr2, arr3):
        """
        :type arr1: List[int]
        :type arr2: List[int]
        :type arr3: List[int]
        :rtype: List[int]
        """
        result = []
        i, j, k = 0, 0, 0
        while i != len(arr1) and j != len(arr2) and k != len(arr3):
            if arr1[i] == arr2[j] == arr3[k]:
                result.append(arr1[i])
                i += 1
                j += 1
                k += 1
            else:
                curr = max(arr1[i], arr2[j], arr3[k])
                while i != len(arr1) and arr1[i] < curr:
                    i += 1
                while j != len(arr2) and arr2[j] < curr:
                    j += 1
                while k != len(arr3) and arr3[k] < curr:
                    k += 1
        return result

s = Solution1()

arr1 = [1,2,3,4,5]
arr2 = [1,2,5,7,9]
arr3 = [1,3,4,5,8]
assert s.arraysIntersection(arr1, arr2, arr3) == [1,5]

import functools

class Solution2(object):
    def arraysIntersection(self, arr1, arr2, arr3):
        """
        :type arr1: List[int]
        :type arr2: List[int]
        :type arr3: List[int]
        :rtype: List[int]
        """
        intersect = functools.reduce(set.intersection, map(set, [arr2, arr3]))
        return [x for x in arr1 if x in intersect]

s = Solution2()

arr1 = [1,2,3,4,5]
arr2 = [1,2,5,7,9]
arr3 = [1,3,4,5,8]
assert s.arraysIntersection(arr1, arr2, arr3) == [1,5]

class Solution3(object):
    def arraysIntersection(self, arr1, arr2, arr3):
        """
        :type arr1: List[int]
        :type arr2: List[int]
        :type arr3: List[int]
        :rtype: List[int]
        """
        val = [0] * 2001
        for i in arr1:
            val[i] += 1
        for i in arr2:
            val[i] += 1
        for i in arr3:
            val[i] += 1
        res = []
        for i,v in enumerate(val):
            if v == 3:
                res.append(i)
        return res

s = Solution3()

arr1 = [1,2,3,4,5]
arr2 = [1,2,5,7,9]
arr3 = [1,3,4,5,8]
assert s.arraysIntersection(arr1, arr2, arr3) == [1,5]

See also:

https://leetcode.com/problems/intersection-of-three-sorted-arrays